#include<iostream>

using namespace std;

long long Fibinacci(int n){
	int result[2] = {0, 1};
	if ( n<2 ){
		return result[n-1];	
	}
	
	long long firstOne = 0;
	long long firstTwo = 1;	
	long long tmp = 0;
	for ( int i =2; i<= n; i++ ){
		tmp = firstOne+firstTwo;
		firstOne = firstTwo;
		firstTwo = tmp; 
	}
	return tmp;
}

int main(void){
	cout << Fibinacci(5) << endl;
	return 0;
}

// 斐波拉切数组由于存在大量的重复计算，采用递归实现时效率不高，因此使用循环操作
// 变相问题：青蛙跳台阶（可以跳１级，２级）
//          用2*１的矩阵采用横着、竖着去覆盖更大的矩阵